package leetcode.string;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

/**
 * 3. 无重复字符的最长子串
 *
 */
public class LongestSubstring {

    public static void main(String[] args) {
        LongestSubstring solution = new LongestSubstring();
//        String str = "abcabcbb";
        String str = "abca12345attttt";
        int index = solution.lengthOfLongestSubstring(str);
        System.out.println(index);
    }

    /**
     * 自己写的
     *
     * @param s 字符串
     * @return
     */
    public int lengthOfLongestSubstring0(String s) {
        int n = s.length();
        if (n == 1) {
            return 1;
        }
        int maxLen = 0;
        int left = 0;
        int right = 0;
        Map<Character, Integer> map = new HashMap<>();
        while (right < n) {
            char rightValue = s.charAt(right);
            if (!map.containsKey(rightValue)) {
                map.put(rightValue, right);
                right++;
            } else {
                char leftValue = s.charAt(left);
                map.remove(leftValue);
                left++;
            }
            maxLen = Math.max(maxLen, right - left);
        }
        return maxLen;
    }


    /**
     * 使用 HashSet的改进版本
     *
     * @param s 字符串
     * @return
     */
    public int lengthOfLongestSubstring1(String s) {
        int n = s.length();
        if (n == 1) {
            return 1;
        }
        int maxLen = 0;
        int left = 0;
        int right = 0;
        Set<Character> set = new HashSet<>();
        while (right < n) {
            char rightValue = s.charAt(right);
            if (!set.contains(rightValue)) {
                set.add(rightValue);
                right++;
            } else {
                char leftValue = s.charAt(left);
                set.remove(leftValue);
                left++;
            }
            maxLen = Math.max(maxLen, right - left);
        }
        return maxLen;
    }


    /**
     * 官方解法
     *
     * @param s 字符串
     * @return
     */
    public int lengthOfLongestSubstring(String s) {
        HashMap<Character, Integer> map = new HashMap<>();
        int max = 0, start = 0;
        for (int end = 0; end < s.length(); end++) {
            char ch = s.charAt(end);
            if (map.containsKey(ch)) {
                // 精华所在
                start = Math.max(map.get(ch) + 1, start);
            }
            max = Math.max(max, end - start + 1);
            map.put(ch, end);
        }
        return max;
    }


}
